"""
算法准备：动态规划和贪心算法
"""

weight = [4, 3, 2, 6, 5]
value = [3, 4, 6, 7, 9]
maxweight = 8
# 只输出最大价值
def ZeroOnePack_Simple(W, V, MW):  # 0-1背包
    # 存储最大价值的一维数组
    valuelist = [0] * (MW + 1)
    # 开始计算
    for ii in range(len(W)):  # 从第一个物品
        copyvalue = valuelist.copy()
        for jj in range(MW + 1):  # 从重量0
            if jj >= W[ii]:  # 如果重量大于物品重量
                copyvalue[jj] = max(valuelist[jj - W[ii]] + V[ii], valuelist[jj])  # 选中第ii个物品和不选中，取大的
        valuelist = copyvalue.copy()  # 更新
    return '最大价值：', valuelist[-1]

#  也输出选择物品的编号
def ZeroOnePack(W, V, MW):  # 0-1背包
    # 存储最大价值的一维数组
    valuelist = [0] * (MW + 1)
    # 存储物品编号的字典
    codedict = {i: [] for i in range(0, MW + 1)}
    # 开始计算
    for ii in range(len(W)):  # 从第一个物品
        copyvalue = valuelist.copy()
        copydict = codedict.copy()
        for jj in range(MW + 1):  # 从重量0
            if jj >= W[ii]:  # 如果重量大于物品重量
                copyvalue[jj] = max(valuelist[jj - W[ii]] + V[ii], valuelist[jj])  # 选中第ii个物品和不选中，取大的
                # 输出被选中的物品编号
                if copyvalue[jj] > valuelist[jj]:
                    copydict[jj] = [ii]
                    for hh in codedict[jj - W[ii]]:
                        copydict[jj].append(hh)
        codedict = copydict.copy()  # 更新
        valuelist = copyvalue.copy()  # 更新
    print('所需物品：', sorted([1 + code for code in codedict[MW]]))
    return '最大价值：', valuelist[-1]

print(ZeroOnePack_Simple(weight, value, maxweight))
